package InterfaceOffer;

import java.util.ArrayList;
import java.util.List;

public class Practice1 {

    public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<Integer>();
        List<Integer> list2 = new ArrayList<Integer>();
        List<Integer> list3 = new ArrayList<Integer>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list2.add(4);
        list2.add(5);
        list2.add(6);
        list3.add(7);
        list3.add(8);
        list3.add(9);
        List<List<Integer>> nums = new ArrayList<List<Integer>>();
        nums.add(list1);
        nums.add(list2);
        nums.add(list3);
        int[] diagonalOrder = findDiagonalOrder(nums);
        for(int i = 0 ; i < diagonalOrder.length ; i++){
            System.out.print(diagonalOrder[i]+" ");
        }
    }

    public static int[] findDiagonalOrder(List<List<Integer>> nums) {
        int edge = findEdge(nums);
        int[][] matrix = buildMatrix(nums,edge);
        List<Integer> ans = new ArrayList<Integer>();
        for(int index = 0 ; index < edge ; index++){
            int i = index;
            for(int j = 0 ; j <= index ; j++){
                if(matrix[i][j]!=0){
                    ans.add(matrix[i][j]);
                }
                i--;
            }
        }
        for(int colIndex = 1 ; colIndex < edge ; colIndex++){
            int j = colIndex;
            for(int i = edge-1 ; i >= colIndex ; i--){
                if(matrix[i][j]!=0){
                    ans.add(matrix[i][j]);
                }
                j++;
            }
        }
        int[] ints = ans.stream().mapToInt(Integer::valueOf).toArray();
        return ints;
    }
    public static int findEdge(List<List<Integer>> nums){
        int max = nums.size();
        for(List<Integer> list : nums){
            max = Math.max(max,list.size());
        }
        return max;
    }
    public static int[][] buildMatrix(List<List<Integer>> nums,int edge){
        int[][] matrix = new int[edge][edge];
        int i = 0;
        for(List<Integer> list : nums){
            for(int j = 0 ; j < edge ; j++){
                try{
                    int num = list.get(j);
                    matrix[i][j] = num;
                }catch(Exception e){
                    matrix[i][j] = 0;
                }
            }
            i++;
        }
        return matrix;
    }
}
